// 《围棋》作者版权所有。版权所有。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

package runtime

import (
	"runtime/internal/atomic"
	"unsafe"
)

// profBuf是用于分析事件的无锁缓冲区，
// 可供一个读写器同时使用。
// 写入程序可能是在没有用户g的情况下运行的信号处理程序。
// 假定读卡器是用户g。
// 
// 每个记录的事件对应一个固定大小的头、一个
// UINTPTR列表（通常是一个堆栈）和一个不安全的.Pointer标记。
// 头和UINTPTR存储在循环缓冲区数据中，
// 标记存储在循环缓冲区标记中，并行运行。
// 在循环缓冲区数据中，每个事件取2+hdrsize+len（stk）
// 字：值2+hdrsize+len（stk），然后是事件的时间，然后是
// hdrsize字给出固定大小的头，然后是len（stk）字
// 用于堆栈。
// 
// 进入标签和数据循环缓冲区的当前有效偏移量
// 用于读写，存储在r和w的高30位和低32位。
// 高32的底位是w中的附加标志位，r中未使用。
// /“有效”偏移量是指读取或写入的总次数，mod 2^长度。
// 缓冲区中的偏移量是缓冲区长度的有效偏移量。
// 要使wrapparound mod 2^length与缓冲区的wrapparound mod length匹配，
// 缓冲区的长度必须是2的幂。
// 
// 如果读卡器赶上了写卡器，则传递给read的标志将控制
// 是否阻止读取，直到有更多数据可用。读取返回一个指向缓冲区数据本身的
// 指针；假定调用方在下一次读取时使用
// 完成该数据。读取偏移量rNext跟踪读取返回的
// 的下一个偏移量。根据定义，r≤ rNext≤ w（在总括之前）、
// 和rNext仅由读卡器使用，因此可以在没有原子的情况下访问。
// 
// 如果写入程序领先于读取器，导致缓冲区填满，
// 将丢弃未来写入，并在输出流中替换为
// 溢出项，其大小为2+hdrsize+1，时间设置为
// 第一次丢弃写入的时间，一个全零字的标题和一个“堆栈”
// 包含一个字，即丢弃的写入数。
// 
// 在缓冲区填满和缓冲区变为足够空
// 以容纳更多数据之间，溢出项作为挂起的溢出
// 项存储在溢出和溢出时间字段中。未决溢出
// 条目可由写入程序或
// 读取器转换为真实记录。如果调用writer写入新记录，并发现输出缓冲区中有空间容纳挂起的溢出项和新记录，则writer会将挂起的溢出项和新的
// 记录发送到缓冲区中。如果调用读取器读取数据，并发现输出缓冲区为空，但存在挂起的溢出
// 项，读取器将返回挂起的
// 溢出项的合成记录。
// 
// 只有编写器可以创建或添加挂起的溢出项，但
// 读卡器或编写器都可以清除挂起的溢出项。
// 挂起的溢出项由'overflow'的低32位
// 表示丢弃的写入数，overflowTime表示第一次丢弃写入的时间。“溢出”
// 的高32位在每次低32位从零转换到非零
// 时递增，反之亦然。此序列号避免了使用
// 比较和交换以协调读写器之间的ABA问题。
// 仅当溢出的低32位为
// 零时，即在
// 中没有挂起的溢出项时，才会写入溢出时间，以准备创建新的溢出项。因此，读者可以使用
// 
// for{
// overflow=load（&b.overflow）
// /如果uint32（overflow）=0{
// /没有挂起的条目
// /中断
// /}
// 如果cas（&b.overflow，overflow，（（overflow>>32）+1）<<32）{
// 
// 中断
// }
// }
// 如果uint32（overflow）>0{
// 为uint32（overflow）发出条目，时间
// 
type profBuf struct {
	// 以原子方式访问
	r, w         profAtomic
	overflow     uint64
	overflowTime uint64
	eof          uint32

	// 不可变（不包括切片内容）
	hdrsize uintptr
	data    []uint64
	tags    []unsafe.Pointer

	// 由读卡器拥有
	rNext       profIndex
	overflowBuf []uint64 // 用于读卡器返回溢出记录
	wait        note
}

// PROFAMATIC是以原子方式访问的包含profIndex的字。
type profAtomic uint64

// profIndex是如上所述的数据包标签、数据计数和标志位。
type profIndex uint64

const (
	profReaderSleeping profIndex = 1 << 32 // 读卡器正在睡觉，必须被唤醒
	profWriteExtra     profIndex = 1 << 33 // 溢出或等待eof 
)

func (x *profAtomic) load() profIndex {
	return profIndex(atomic.Load64((*uint64)(x)))
}

func (x *profAtomic) store(new profIndex) {
	atomic.Store64((*uint64)(x), uint64(new))
}

func (x *profAtomic) cas(old, new profIndex) bool {
	return atomic.Cas64((*uint64)(x), uint64(old), uint64(new))
}

func (x profIndex) dataCount() uint32 {
	return uint32(x)
}

func (x profIndex) tagCount() uint32 {
	return uint32(x >> 34)
}

// countSub减去从profIndex.dataCount或profIndex.tagCount获得的两个计数，
// 假设它们之间的间隔不超过2^29（保证，因为它们永远不会超过
// len（数据）或len（标记）分开。
// tagCount在2^30处换行，而dataCount在2^32处换行。
// 此函数对两者都有效。
func countSub(x, y uint32) int {
	// x-y是32位有符号或30位有符号的；符号扩展到32位并转换为int。
	return int(int32(x-y) << 2 >> 2)
}

// addCountsAndClearFlags返回压缩形式的“x+（数据、标记）-所有标志“.
func (x profIndex) addCountsAndClearFlags(data, tag int) profIndex {
	return profIndex((uint64(x)>>34+uint64(uint32(tag)<<2>>2))<<34 | uint64(uint32(x)+uint32(data)))
}

// hasOverflow报告b是否有任何未决的溢出记录。
func (b *profBuf) hasOverflow() bool {
	return uint32(atomic.Load64(&b.overflow)) > 0
}

// takeOverflow使用未决的溢出记录，返回溢出计数
// 和第一次溢出的时间。
// 当读卡器调用时，它正在与增量溢出竞争。
func (b *profBuf) takeOverflow() (count uint32, time uint64) {
	overflow := atomic.Load64(&b.overflow)
	time = atomic.Load64(&b.overflowTime)
	for {
		count = uint32(overflow)
		if count == 0 {
			time = 0
			break
		}
		// 增量生成，以低位清除溢出计数。
		if atomic.Cas64(&b.overflow, overflow, ((overflow>>32)+1)<<32) {
			break
		}
		overflow = atomic.Load64(&b.overflow)
		time = atomic.Load64(&b.overflowTime)
	}
	return uint32(overflow), time
}

// 增量溢出现在只记录一次溢出。
// 它正在与读卡器中可能的接管流竞争。
func (b *profBuf) incrementOverflow(now int64) {
	for {
		overflow := atomic.Load64(&b.overflow)

		// 一旦我们看到b.overflow达到0，它就稳定了：没有其他人在脚下更改它。
		// 我们需要如果我们将b.overflow从0递增，则设置溢出时间。
		if uint32(overflow) == 0 {
			// 首先存储溢出时间，以便溢出时它始终可用！=0。
			atomic.Store64(&b.overflowTime, uint64(now))
			atomic.Store64(&b.overflow, (((overflow>>32)+1)<<32)+1)
			break
		}
		// 否则我们将与读者
		// 竞争，后者希望将b.overflow设置为0。
		// 出于偏执，请留下2-1一个粘性overflow值，
		// 避免环绕。极不可能。
		if int32(overflow) == -1 {
			break
		}
		if atomic.Cas64(&b.overflow, overflow, overflow+1) {
			break
		}
	}
}

// newproffuf返回一个新的分析缓冲区，其中有空间容纳
// 一个hdrsize字头和一个至少包含bufwords字的缓冲区。
func newProfBuf(hdrsize, bufwords, tags int) *profBuf {
	if min := 2 + hdrsize + 1; bufwords < min {
		bufwords = min
	}

	// 缓冲区大小必须是2的幂，这样我们就不必使用
	// w很抱歉uint32 wrapparound更改了缓冲区内的有效位置
	// 我们存储了30位计数；限制为28 
	// 为中间计算提供了一些空间。
	if bufwords >= 1<<28 || tags >= 1<<28 {
		throw("newProfBuf: buffer too large")
	}
	var i int
	for i = 1; i < bufwords; i <<= 1 {
	}
	bufwords = i
	for i = 1; i < tags; i <<= 1 {
	}
	tags = i

	b := new(profBuf)
	b.hdrsize = uintptr(hdrsize)
	b.data = make([]uint64, bufwords)
	b.tags = make([]unsafe.Pointer, tags)
	b.overflowBuf = make([]uint64, 2+b.hdrsize+1)
	return b
}

// canWriteRecord报告缓冲区是否有空间
// 用于一个带有sta的连续记录长度的ck nstk.
func (b *profBuf) canWriteRecord(nstk int) bool {
	br := b.r.load()
	bw := b.w.load()

	// 标记空间？
	if countSub(br.tagCount(), bw.tagCount())+len(b.tags) < 1 {
		return false
	}

	// 数据空间？
	nd := countSub(br.dataCount(), bw.dataCount()) + len(b.data)
	want := 2 + int(b.hdrsize) + nstk
	i := int(bw.dataCount() % uint32(len(b.data)))
	if i+want > len(b.data) {
		// 无法放入切片的尾部片段。
		// 跳过该部分并在切片的开头重新开始。
		nd -= len(b.data) - i
	}
	return nd >= want
}

// CanWriteTorRecords报告缓冲区是否有空间
// 用于带有sta的两条记录ck长度nstk1，nstk2，按顺序。
// 每条记录必须是连续的，但两条
// 记录不必是连续的（一条可以在缓冲区的末尾
// 另一条可以环绕并从缓冲区的开头开始）.
func (b *profBuf) canWriteTwoRecords(nstk1, nstk2 int) bool {
	br := b.r.load()
	bw := b.w.load()

	// 为标记预留空间？
	if countSub(br.tagCount(), bw.tagCount())+len(b.tags) < 2 {
		return false
	}

	// 为数据预留空间？
	nd := countSub(br.dataCount(), bw.dataCount()) + len(b.data)

	// 第一条记录
	want := 2 + int(b.hdrsize) + nstk1
	i := int(bw.dataCount() % uint32(len(b.data)))
	if i+want > len(b.data) {
		// 无法放入切片的尾部片段。
		// 跳过该部分并从切片的开头重新开始。
		nd -= len(b.data) - i
		i = 0
	}
	i += want
	nd -= want

	// 第二条记录
	want = 2 + int(b.hdrsize) + nstk2
	if i+want > len(b.data) {
		// 无法放入切片的尾部片段。
		// 跳过该选项，从切片的开始处重新开始。
		nd -= len(b.data) - i
		i = 0
	}
	return nd >= want
}

// 将一个条目写入分析缓冲区b。
// 该条目以一个固定的hdr开始，该hdr必须具有
// 长度b.hdrsize，后跟一个可变大小的堆栈
// 和一个标记指针*tagPtr（如果tagPtr为零，则为零）.
// 不允许写入障碍，因为这可能是从信号处理程序调用的。
func (b *profBuf) write(tagPtr *unsafe.Pointer, now int64, hdr []uint64, stk []uintptr) {
	if b == nil {
		return
	}
	if len(hdr) > int(b.hdrsize) {
		throw("misuse of profBuf.write")
	}

	if hasOverflow := b.hasOverflow(); hasOverflow && b.canWriteTwoRecords(1, len(stk)) {
		// 为溢出记录和正在写入的记录留出空间。
		// 如果读卡器尚未到达溢出记录，则写入该记录。
		// 仅与读卡器竞争，而不是与其他写入器竞争。
		count, time := b.takeOverflow()
		if count > 0 {
			var stk [1]uintptr
			stk[0] = uintptr(count)
			b.write(nil, int64(time), nil, stk[:])
		}
	} else if hasOverflow || !b.canWriteRecord(len(stk)) {
		// 挂起的溢出没有写入溢出和新记录的空间
		b.incrementOverflow(now)
		b.wakeupExtra()
		return
	}

	// 还有空间：写下记录。
	br := b.r.load()
	bw := b.w.load()

	// 分析标记
	// 
	// 标记是指针，但我们不能在此处运行写屏障。
	// 我们已经中断了gp的操作系统级执行，但是
	// 运行时仍然认为gp正在执行。实际上，我们正在运行
	// 来代替真正的gp。由于gp是
	// 可以覆盖gp.labels的唯一goroutine，因此在
	// 期间gp.labels的值是稳定的。此信号处理程序：当
	// 我们完成执行时，仍然可以从gp访问它。如果GC正在进行中，它必须
	// 保持gp.labels处于活动状态，因为gp.labels可以从gp访问。
	// 如果gp要覆盖gp.labels，则删除障碍将使该指针保持阴影，这将为正在进行的GC保留该指针，因此一切正常。任何未来的GC都会看到我们在扫描b.tags（heap-allocated）时复制的
	// 值。
	// 我们安排这里的存储总是覆盖一个nil，
	// 因此在b.tags[wt]上不需要删除障碍。
	wt := int(bw.tagCount() % uint32(len(b.tags)))
	if tagPtr != nil {
		*(*uintptr)(unsafe.Pointer(&b.tags[wt])) = uintptr(unsafe.Pointer(*tagPtr))
	}

	// 主记录。
	// 它必须适合切片的一个连续部分，因此如果它在结尾处不适合，
	// 保留一个倒带标记（0），并在切片的开头重新开始。
	wd := int(bw.dataCount() % uint32(len(b.data)))
	nd := countSub(br.dataCount(), bw.dataCount()) + len(b.data)
	skip := 0
	if wd+2+int(b.hdrsize)+len(stk) > len(b.data) {
		b.data[wd] = 0
		skip = len(b.data) - wd
		nd -= skip
		wd = 0
	}
	data := b.data[wd:]
	data[0] = uint64(2 + b.hdrsize + uintptr(len(stk))) // 长度
	data[1] = uint64(now)                               // 时间戳
	// 头，零填充
	i := uintptr(copy(data[2:2+b.hdrsize], hdr))
	for ; i < b.hdrsize; i++ {
		data[2+i] = 0
	}
	for i, pc := range stk {
		data[2+b.hdrsize+uintptr(i)] = uint64(pc)
	}

	for {
		// 提交写入。
		// 与读卡器在b.w中设置标志位，以避免丢失唤醒。
		old := b.w.load()
		new := old.addCountsAndClearFlags(skip+2+len(stk)+int(b.hdrsize), 1)
		if !b.w.cas(old, new) {
			continue
		}
		// 如果有读者，请唤醒它。
		if old&profReaderSleeping != 0 {
			notewakeup(&b.wait)
		}
		break
	}
}

// close表示缓冲区上不再有写操作。
// 一旦从缓冲区读取了所有数据，reads将返回eof=true。
func (b *profBuf) close() {
	if atomic.Load(&b.eof) > 0 {
		throw("runtime: profBuf already closed")
	}
	atomic.Store(&b.eof, 1)
	b.wakeupExtra()
}

// 必须在设置一个“额外”
// 原子字段b.overflow或b.eof后调用wakeupExtra。
// 它记录b.w中的更改，并在需要时唤醒读卡器。
func (b *profBuf) wakeupExtra() {
	for {
		old := b.w.load()
		new := old | profWriteExtra
		if !b.w.cas(old, new) {
			continue
		}
		if old&profReaderSleeping != 0 {
			notewakeup(&b.wait)
		}
		break
	}
}

// profBufReadMode指定在没有可读取数据时是否阻塞。
type profBufReadMode int

const (
	profBufBlocking profBufReadMode = iota
	profBufNonBlocking
)

var overflowTag [1]unsafe.Pointer // 始终为零

func (b *profBuf) read(mode profBufReadMode) (data []uint64, tags []unsafe.Pointer, eof bool) {
	if b == nil {
		return nil, nil, true
	}

	br := b.rNext

	// 提交先前读取，将戒指的该部分返回给写入者。
	// 首先清除已读取的标记，以避免保留
	// 超出所需时间的内存
	// 因此b.write可以假定它总是覆盖
	// 无标记项（请参阅b.write中的注释）。
	rPrev := b.r.load()
	if rPrev != br {
		ntag := countSub(br.tagCount(), rPrev.tagCount())
		ti := int(rPrev.tagCount() % uint32(len(b.tags)))
		for i := 0; i < ntag; i++ {
			b.tags[ti] = nil
			if ti++; ti == len(b.tags) {
				ti = 0
			}
		}
		b.r.store(br)
	}

Read:
	bw := b.w.load()
	numData := countSub(bw.dataCount(), br.dataCount())
	if numData == 0 {
		if b.hasOverflow() {
			// 没有要读取的数据，但有溢出要报告。
			// 与写入程序竞争，将b.overflow刷新为真实记录。
			count, time := b.takeOverflow()
			if count == 0 {
				// 比赛输了，再绕一圈。
				goto Read
			}
			// 赢得比赛，报告溢出。
			dst := b.overflowBuf
			dst[0] = uint64(2 + b.hdrsize + 1)
			dst[1] = uint64(time)
			for i := uintptr(0); i < b.hdrsize; i++ {
				dst[2+i] = 0
			}
			dst[2+b.hdrsize] = uint64(count)
			return dst[:2+b.hdrsize+1], overflowTag[:1], false
		}
		if atomic.Load(&b.eof) > 0 {
			// 无数据，无溢出，EOF集合：完成。
			return nil, nil, true
		}
		if bw&profWriteExtra != 0 {
			// 作者声称发布了额外信息（溢出或eof）。
			// 尝试清除通知，然后再次检查。
			// 如果我们未能清除通知，则表示b.w已更改，
			// 因此我们仍需要再次检查。
			b.w.cas(bw, bw&^profWriteExtra)
			goto Read
		}

		// 现在没什么可看的。
		// 根据模式返回或睡眠。
		if mode == profBufNonBlocking {
			return nil, nil, false
		}
		if !b.w.cas(bw, bw|profReaderSleeping) {
			goto Read
		}
		// 致力于睡眠。
		notetsleepg(&b.wait, -1)
		noteclear(&b.wait)
		goto Read
	}
	data = b.data[br.dataCount()%uint32(len(b.data)):]
	if len(data) > numData {
		data = data[:numData]
	} else {
		numData -= len(data) // 可用于环绕记录
	}
	skip := 0
	if data[0] == 0 {
		// 环绕记录。回到拳台的开头。
		skip = len(data)
		data = b.data
		if len(data) > numData {
			data = data[:numData]
		}
	}

	ntag := countSub(bw.tagCount(), br.tagCount())
	if ntag == 0 {
		throw("runtime: malformed profBuf buffer - tag and data out of sync")
	}
	tags = b.tags[br.tagCount()%uint32(len(b.tags)):]
	if len(tags) > ntag {
		tags = tags[:ntag]
	}

	// 计算整个数据记录，直到完成数据或标记。
	// 它们在缓冲区中始终同步，但由于片的结尾
	// 概括，我们可能需要提前停止，并在下一次调用中返回其余的
	// 。
	di := 0
	ti := 0
	for di < len(data) && data[di] != 0 && ti < len(tags) {
		if uintptr(di)+uintptr(data[di]) > uintptr(len(data)) {
			throw("runtime: malformed profBuf buffer - invalid size")
		}
		di += int(data[di])
		ti++
	}

	// 记住我们返回了多少，以便在下次通话时提交阅读。
	b.rNext = br.addCountsAndClearFlags(skip+di, ti)

	if raceenabled {
		// 在运行时匹配racereleasemerge\u setProfLabel，
		// 以便在运行时设置标签\u setProfLabel 
		// 被视为在调用方使用标签
		// 之前发生。labelSync本身上的同步对于种族检测器来说是虚构的
		// 。实际的同步是通过以下事实来处理的：信号处理程序只从当前的
		// goroutine读取，并使用原子来写入更新的队列索引，
		// 然后从信号处理程序缓冲区读取的数据使用
		// 原子来读取这些队列索引。
		raceacquire(unsafe.Pointer(&labelSync))
	}

	return data[:di], tags[:ti], false
}
